%%%
\vspace{1cm}
{\bf Longest Common Subsequence (LCS)}:\\

Dat un {\c s}ir de numere naturale determina{\c t}i cel mai lung sub{\c s}ir cresc{\u a}tor al acestuia.\\

{\bf Cerin{\c t}e}:
\begin{enumerate}
\item (2 puncte) Care este solu{\c t}ia problemei pentru {\c s}irul $7, 3, 8, 4, 2, 6$?
\item (2 puncte) Se consider{\u a} $f:\mathbb{N}\rightarrow\mathbb{N}$, unde $f(i)$ reprezint{\u a} lungimea celui mai lung sub{\c s}ir p{\^ a}n{\u a} la pozi{\c t}ia $i$. Calcula{\c t}i $f(i)$ pentru $i\in\{0,1,2,3,4,5\}$ {\^ i}n {\c s}irul $7, 3, 8, 4, 2, 6$.
\item (2 puncte) Care este complexitatea timp a algoritmului care calculeaz{\u a} func{\c t}ia $f$? Argumenta{\c t}i r{\u a}spunsul.
\item (2 puncte) Care este formula de recuren{\c t}{\u a} care rezolv{\u a} problema {\bf LCS}? (Utiliza{\c t}i func{\c t}ia $f$.)
\item (2 puncte) Scrie{\c t}i un algoritm care rezolv{\u a} problema {\bf LCS}. Se consider{\u a} c{\u a} exist{\u a} deja o implementare a func{\c t}iei $f$.
\end{enumerate}
%%%


%%%
\vspace{1cm}
{\bf Longest Common Subsequence (LCS)}:\\

Dat un {\c s}ir de numere naturale determina{\c t}i cel mai lung sub{\c s}ir cresc{\u a}tor al acestuia.\\

{\bf Cerin{\c t}e}:
\begin{enumerate}
\item (2 puncte) Care este solu{\c t}ia problemei pentru {\c s}irul $6, 5, 3, 2, 7, 8, 1, 10$?
\item (2 puncte) Se consider{\u a} $f:\mathbb{N}\rightarrow\mathbb{N}$, unde $f(i)$ reprezint{\u a} lungimea celui mai lung sub{\c s}ir p{\^ a}n{\u a} la pozi{\c t}ia $i$. Calcula{\c t}i $f(i)$ pentru $i\in\{0,1,2,3,4,5,6,7\}$ {\^ i}n {\c s}irul $6, 5, 3, 2, 7, 8, 1, 10$.
\item (2 puncte) Desena{\c t}i graful aciclic (orientat) corespunz{\u a}tor func{\c t}iei $f$, astfel {\^ i}nc{\^ a}t unei valori $v$ din {\c s}ir {\^ i}i corespunde un nod, iar fiec{\u a}rei perechi $(v', v)$ {\^ i}i corespunde o muchie, unde $v'$ apare {\^ i}naintea lui $v$ {\^ i}n {\c s}ir {\c s}i este mai mic dec{\^ a}t acesta.
\item (2 puncte) Care este formula de recuren{\c t}{\u a} care rezolv{\u a} problema {\bf LCS}? (Utiliza{\c t}i func{\c t}ia $f$.)
\item (2 puncte) Scrie{\c t}i un algoritm care implementeaz{\u a} func{\c t}ia $f$.
\end{enumerate}
%%%

%%%
\vspace{1cm}
{\bf Longest Common Subsequence (LCS)}:\\

Dat un {\c s}ir de numere naturale determina{\c t}i cel mai lung sub{\c s}ir cresc{\u a}tor al acestuia.\\

{\bf Cerin{\c t}e}:
\begin{enumerate}
\item (2 puncte) Care este solu{\c t}ia problemei pentru {\c s}irul $6, 5, 3, 2, 7, 8, 1, 10$?
\item (2 puncte) Se consider{\u a} $f:\mathbb{N}\rightarrow\mathbb{N}$, unde $f(i)$ reprezint{\u a} lungimea celui mai lung sub{\c s}ir p{\^ a}n{\u a} la pozi{\c t}ia $i$. Calcula{\c t}i $f(i)$ pentru $i\in\{0,1,2,3,4,5,6,7\}$ {\^ i}n {\c s}irul $6, 5, 3, 2, 7, 8, 1, 10$.
\item (2 puncte) Care este complexitatea timp a algoritmului care calculeaz{\u a} func{\c t}ia $f$? Argumenta{\c t}i r{\u a}spunsul.
\item (2 puncte) Care este formula de recuren{\c t}{\u a} care rezolv{\u a} problema {\bf LCS}? (Utiliza{\c t}i func{\c t}ia $f$.)
\item (2 puncte) Scrie{\c t}i un algoritm care rezolv{\u a} problema {\bf LCS}. Se consider{\u a} c{\u a} exist{\u a} deja o implementare a func{\c t}iei $f$.
\end{enumerate}
%%%

%%%
\vspace{1cm}
{\bf Longest Common Subsequence (LCS)}:\\

Dat un {\c s}ir de numere naturale determina{\c t}i cel mai lung sub{\c s}ir cresc{\u a}tor al acestuia.\\

{\bf Cerin{\c t}e}:
\begin{enumerate}
\item (2 puncte) Care este solu{\c t}ia problemei pentru {\c s}irul $7, 3, 8, 4, 2, 6$?
\item (2 puncte) Se consider{\u a} $f:\mathbb{N}\rightarrow\mathbb{N}$, unde $f(i)$ reprezint{\u a} lungimea celui mai lung sub{\c s}ir p{\^ a}n{\u a} la pozi{\c t}ia $i$. Calcula{\c t}i $f(i)$ pentru $i\in\{0,1,2,3,4,5\}$ {\^ i}n {\c s}irul $7, 3, 8, 4, 2, 6$.
\item (2 puncte) Desena{\c t}i graful aciclic (orientat) corespunz{\u a}tor func{\c t}iei $f$, astfel {\^ i}nc{\^ a}t unei valori $v$ din {\c s}ir {\^ i}i corespunde un nod, iar fiec{\u a}rei perechi $(v', v)$ {\^ i}i corespunde o muchie, unde $v'$ apare {\^ i}naintea lui $v$ {\^ i}n {\c s}ir {\c s}i este mai mic dec{\^ a}t acesta.
\item (2 puncte) Care este formula de recuren{\c t}{\u a} care rezolv{\u a} problema {\bf LCS}? (Utiliza{\c t}i func{\c t}ia $f$.)
\item (2 puncte) Scrie{\c t}i un algoritm care implementeaz{\u a} func{\c t}ia $f$.
\end{enumerate}
%%%
